package com.bigshen.algorithm.bStack.solution01ValidParentheses;

import java.util.Stack;

/**
 * 20. Valid Parentheses
 *
 * Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
 *
 * An input string is valid if:
 *
 * Open brackets must be closed by the same type of brackets.
 * Open brackets must be closed in the correct order.
 *  
 *
 * Example 1:
 * Input: s = "()"
 * Output: true
 *
 * Example 2:
 * Input: s = "()[]{}"
 * Output: true
 *
 * Example 3:
 * Input: s = "(]"
 * Output: false
 *
 * Example 4:
 * Input: s = "([)]"
 * Output: false
 *
 * Example 5:
 * Input: s = "{[]}"
 * Output: true
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/valid-parentheses
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 
 *  思路：
 *  使用栈： 
 *    遇到左括号入栈，
 *    遇到右括号出栈并与之配对，不能配对则为不合法；
 *    最后栈不为空表示没有没有配对的，也不合法；
 * 
 */
public class Solution {

    public boolean isValid(String s) {

        if (null == s || s.length() < 1) {
            return true;
        }

        Stack<Character> stack = new Stack();

        char[] array = s.toCharArray();
        for (Character element : array) {

            // 遇到左括号，入栈
            if (element.equals('{') || element.equals('[') || element.equals('(')) {
                stack.push(element);
            }

            // 遇到右括号，栈顶出栈相匹配
            if (element.equals('}')) {
                if (stack.isEmpty() || !stack.pop().equals('{')) {
                    return false;
                }
                continue;
            }
            if (element.equals(']')) {
                if (stack.isEmpty() || !stack.pop().equals('[')) {
                    return false;
                }
                continue;
            }
            if (element.equals(')')) {
                if (stack.isEmpty() || !stack.pop().equals('(')) {
                    return false;
                }
                continue;
            }
        }

        return stack.isEmpty();

    }

    public static void main(String[] args) {


        String str = "()";
        System.out.println(new Solution().isValid(str));

    }

}
